数学 : 漸化式

漸化式とは

各項がそれ以前の項の函数として定まるという意味で数列を再帰的に定める等式。再帰関係式

英: recurrence relation

漸化式の例

例1) フィボナッチ数列

$ F_{n+2} = F_{n+1}+F_n, \ F_0 = 0, \ F_1 = 1

例2)

$ A_{n+1} = 2A_{n}, \ A_1 = 1

上記の漸化式を解くと、 $ A_n = 2^{n-1} となる

漸化式の使用例 : 母関数

$ f(x) = \sum_{k=0}^{\infty} a_k x^k

漸化式の応用例) sin, cosのn乗を求める

$ sin^n x, cos^n xを求める際には漸化式を使う

$ I_n = \int_0^{\frac{\pi}{2}} sin^n x dx

$ 初期条件 : I_0 = \frac{\pi}{2}, I_1 = 1

導出)

$ I_n = \int_0^{\frac{\pi}{2}} sin x \cdot sin^{n-1} x dx

上記の右辺に部分積分を適用する

漸化式を総和と組み合わせた例

$ S_n = \sum_{k=0}^N{a_k}

総和の式を一般化するには摂動法が使われるらしい